package main.sort.java;

public class SortHeap extends Swap implements Sort {

    @Override
    public void execute(int[] ar) {
        sortHeap(ar, ar.length);
    }

    public void sortHeap(int[] ar, int len) {
        for (int root = (len >> 1) - 1; root >= 0; --root) {
            heapBigTop(ar, root, len);
        }

        for (int heap_len = len - 1; heap_len >= 0; --heap_len) {
            Swap.execute(ar, 0, heap_len);
            heapBigTop(ar, 0, heap_len);
        }
    }

    public void heapBigTop(int[] ar, int root, int len) {
        int left = (root << 1) + 1;

        while (left < len) {
            if (left + 1 < len && ar[left] < ar[left + 1]) {
                left += 1;
            }
            if (ar[root] >= ar[left]) {break;}

            Swap.execute(ar, root, left);
            root = left;
            left = (root << 1) + 1;
        }
    }
}